10273. Магическое множество

Задана последовательность целых чисел a₁, a₂, ..., a_n и целое число m.

Определим хорошей последовательностью целых чисел такую непустую последовательность, что сумма элементов ее любой непустой подпоследовательности делится на m.

Найдите количество хороших подпоследовательностей для заданной последовательности a.

Вход. Первая строка содержит количество тестов t. Первая строка каждого теста содержит два целых числа n (1 ≤ n ≤ 30) и m (1 ≤ m ≤ 1000). Вторая строка содержит n целых чисел a₁, a₂, ..., a_n (1 ≤ a_i ≤ 1000).

Выход. Для каждого теста выведите в отдельной строке одно число – количество искомых подпоследовательностей.

Пример входа	Пример выхода
3 2 3 1 2 2 3 1 3 9 3 9 10 11 12 13 14 15 21 22	0 1 15

РЕШЕНИЕ

математика

Анализ алгоритма

Поскольку сумма элементов любой непустой подпоследовательности заданной последовательности делится на m, то каждый элемент такой последовательности должен делиться на m.

Для заданной последовательности a₁, a₂, ..., a_n найдем элементы, делящиеся на m. Пусть B = {a_i1, a_i2, …, a_icnt} – множество чисел, делящихся на m, их количество равно cnt. Тогда любое подмножество B будет хорошей последовательностью. Число таких подмножеств равно 2^cnt – 1 (исключаем пустое множество).

Пример

Рассмотрим третий тест. Множество чисел B, делящихся на m = 3, имеет вид: B = {9, 12, 15, 21}. Количество чисел, делящихся на 3, равно cnt = 4.

Следовательно число искомых подпоследовательностей равно 2⁴ – 1 = 15.

Реализация алгоритма

Читаем количество тестов tests.

scanf("%d", &tests);

Последовательно обрабатываем тесты.

while (tests--)

{

scanf("%d %d", &n, &m);

В переменной cnt подсчитываем количество чисел, делящихся на m.

cnt = 0;

for (i = 0; i < n; i++)

{

scanf("%d", &a);

if (a % m == 0) cnt++;

}

Вычисляем и выводим ответ res = 2^cnt – 1.

res = (1 << cnt) - 1;

printf("%d\n", res);

}

Java реализация

import java.util.*;

public class Main

{

public static void main(String []args)

{

Scanner con = new Scanner(System.in);

int tests = con.nextInt();

while(tests-- > 0)

{

int n = con.nextInt();

int m = con.nextInt();

int cnt = 0;

for (int i = 0; i < n; i++)

{

int a = con.nextInt();

if (a % m == 0) cnt++;

}

int res = (1 << cnt) - 1;

System.out.println(res);

}

con.close();

}

}